package org.chnxi.study.datastructrues.sort;

import java.util.Arrays;

/**
 * 希尔排序
 */
public class ShellSorting {

    public static void main(String[] args) {
        int[] arr = {8,9,1,7,2,3,5,4,6,0};
        System.out.println("原始数组："+Arrays.toString(arr));
        shellSortByStep(arr);

        System.out.println("直接实现[交换方式]：");
        int[] arr2 = {8,9,1,7,2,3,5,4,6,0};
        shellSort(arr2);
        System.out.println("排序结果："+Arrays.toString(arr2));

        System.out.println("直接实现[移位方式]：");
        int[] arr3 = {8,9,1,7,2,3,5,4,6,0};
        shellSort2(arr3);
        System.out.println("排序结果："+Arrays.toString(arr2));

        System.out.println("测试大量数据的执行耗时[交换方式]：");
        int[] randomArr = new int[80000];
        for (int i =0; i<80000; i++){
            randomArr[i] = (int) (Math.random()*80000);
        }

        long start = System.currentTimeMillis();
        shellSort(randomArr);
        long end = System.currentTimeMillis();
        System.out.println("执行耗时："+(end - start));


        System.out.println("测试大量数据的执行耗时[移位方式]：");
        int[] randomArr2 = new int[80000];
        for (int i =0; i<80000; i++){
            randomArr2[i] = (int) (Math.random()*80000);
        }

        long start2 = System.currentTimeMillis();
        shellSort2(randomArr2);
        long end2 = System.currentTimeMillis();
        System.out.println("执行耗时："+(end2 - start2));

    }

    /**
     * 交换方式
     * @param arr
     */
    public static void shellSortByStep(int[] arr){

        int tmp = 0;

        //第一轮，将10个数据分成5组
        for (int i = 5; i < arr.length; i++){
            //遍历各组中所有的元素（共5组，每组有两个元素），步长5
            for (int j = i - 5; j >= 0; j -= 5){
                //如果当前元素大于加长补偿后的那个元素，说明需要交换
                if(arr[j] > arr[j+5]){
                    tmp = arr[j];
                    arr[j] = arr[j+5];
                    arr[j+5] = tmp;
                }
            }
        }
        System.out.println("第一步："+ Arrays.toString(arr));

        //第二轮，将10个数据分成2组
        for (int i = 2; i < arr.length; i++){
            //遍历各组中所有的元素（共2组，每组有五个元素），步长5
            for (int j = i - 2; j >= 0; j -= 2){
                //如果当前元素大于加长补偿后的那个元素，说明需要交换
                if(arr[j] > arr[j+2]){
                    tmp = arr[j];
                    arr[j] = arr[j+2];
                    arr[j+2] = tmp;
                }
            }
        }
        System.out.println("第二步："+ Arrays.toString(arr));

        //第三轮，将10个数据分成1组
        for (int i = 1; i < arr.length; i++){
            //遍历各组中所有的元素（共1组），步长1
            for (int j = i - 1; j >= 0; j -= 1){
                //如果当前元素大于加长补偿后的那个元素，说明需要交换
                if(arr[j] > arr[j+1]){
                    tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }
        System.out.println("第三步："+ Arrays.toString(arr));

    }

    /**
     * 交换式
     * @param arr
     */
    public static void shellSort(int[] arr){
        int tmp = 0;

        for (int gap= arr.length/2 ; gap > 0 ; gap /= 2){
            for (int i = gap; i < arr.length; i++){
                for (int j = i - gap; j >= 0; j -= gap){
                    if(arr[j] > arr[j+gap]){
                        tmp = arr[j];
                        arr[j] = arr[j+gap];
                        arr[j+gap] = tmp;
                    }
                }
            }
        }
    }

    /**
     * 移位法
     * @param arr
     */
    public static void shellSort2(int[] arr){
        for (int gap= arr.length/2 ; gap > 0 ; gap /= 2){
            //从第gap个元素，逐个对其所在的组进行直接插入排序
            for(int i=gap; i<arr.length; i++){
                int j = i;
                int tmp = arr[j];
                if(arr[j] < arr[j - gap]){
                    while(j-gap >= 0 && tmp < arr[j-gap]){
                        //移动
                        arr[j] = arr[j-gap];
                        j-=gap;
                    }
                    //当退出循环后找到插入位置
                    arr[j] = tmp;
                }
            }
        }
    }


}
